#include <iostream>
#include <cassert>

using namespace std;

namespace UF2{
	class UnionFind{
		private:
			int *parent;	// 数组,存储其父级节点数值
			int count;
		public:
			UnionFind(int count){
				parent = new int[count];
				this->count = count;
				for(int i = 0; i < count; ++i){
					parent[i] = i;
				}
			}

			~UnionFind(){
				delete[] parent;
			}

			int find(int p){
				// 向上追溯其父节点,直到等于父节点
				assert(p >= 0 && p < count);
				while(p != parent[p]){
					p = parent[p];
				}
				return p;
			}

			bool isConnected(int p, int q){
				return find(p) == find(q);
			}

			void unionElements(int p, int q){
			
				int pRoot = find(p);
				int qRoot = find(q);

				if(pRoot == qRoot){
					return;
				}
				// 一个元素对应根指向另一个元素对应的根
				parent[pRoot] = qRoot;
			}
	};
}
